package com.zlk.algorithm.algorithm.dynamicPlan.twoDimension;

import com.sun.xml.internal.txw2.TXW;

// 最长公共子序列
// 给定两个字符串text1和text2
// 返回这两个字符串的最长 公共子序列 的长度
// 如果不存在公共子序列，返回0
// 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列
//子序列和子串的核心区别在于元素连续性：‌子串要求字符连续且位置固定，子序列仅需保持元素顺序且允许不连续‌。
// 测试链接 : https://leetcode.cn/problems/longest-common-subsequence/
public class Code03_LongestCommonSubsequence {

    //思路展开可能性
    //从最后一个字符出发
    //   S1[]  S2[]
    //  1、 字符不在公共子序列中  return S1[i-1]  S2[j-1]
    //  2、  部门不在    return S1[i-1]  S2[j] |return S1[i]  S2[j-1]
    //  3、  都在       return 1+  S1[i-1] S2[j-1]
    public int longestCommonSubsequence(String text1, String text2) {
        char[] chars1 = text1.toCharArray();
        char[] chars2 = text2.toCharArray();
        int l1 = chars1.length;
        int l2 = chars2.length;
        //return f1(chars1,chars2,l1-1,l2-1);
        //return f2(chars1,chars2,chars1.length,chars2.length);
        int[][] dp = new int[l1 + 1][l2 + 1];
        for (int i = 0; i <= l1; i++) {
            for (int j = 0; j <= l2; j++) {
                dp[i][j] = -1;
            }
        }
        //return f1(chars1,chars2,l1,l2,dp);
        return f4(text1,text2);
    }

    //严格位置依赖的  动态规划 + 空间压缩
    private int f5(String text1, String text2) {
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();

        if(s1.length<s2.length){
            char[] temp = s2;
            s2 = s1;
            s1 = temp;
        }
        //获取较大为s1 较小的为s2
        int len1 = s1.length;
        int len2 = s2.length;
        int[] dp = new int[len2+1];

        for (int i = 1; i <= s1.length; i++) {
            int leftTop = 0;
            for (int j = 1; j <= s2.length; j++) {
                int temp  = dp[j];
                if (s1[i - 1] == s2[j - 1]) {
                    dp[j] = leftTop + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j-1]);
                }
                leftTop = temp;
            }
        }
        return dp[len2];
    }

    // 严格位置依赖的动态规划
    private int f4(String text1, String text2) {
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        int len1 = s1.length;
        int len2 = s2.length;
        int[][] dp = new int[len1+1][len2+1];

        for (int i = 1; i <= s1.length; i++) {
            for (int j = 1; j <= s2.length; j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[len1][len2];
    }




    private int f1(char[] s1, char[] s2, int len1, int len2, int[][] dp) {
        if (len1 == 0 || len2 == 0) {
            return 0;
        }
        if(dp[len1][len2]!=-1){
            return  dp[len1][len2];
        }
        int ans;
        if (s1[len1 - 1] == s2[len2 - 1]) {
            ans = f1(s1, s2, len1 - 1, len2 - 1,dp) + 1;
        } else {
            ans = Math.max(f1(s1, s2, len1 - 1, len2,dp), f1(s1, s2, len1, len2 - 1,dp));
        }
        dp[len1][len2] = ans;
        return ans;
    }

    // s1[前缀长度为len1]对应s2[前缀长度为len2]
    // 最长公共子序列长度
    public static int f2(char[] s1, char[] s2, int len1, int len2) {
        if (len1 == 0 || len2 == 0) {
            return 0;
        }
        int ans;
        if (s1[len1 - 1] == s2[len2 - 1]) {
            ans = f2(s1, s2, len1 - 1, len2 - 1) + 1;
        } else {
            ans = Math.max(f2(s1, s2, len1 - 1, len2), f2(s1, s2, len1, len2 - 1));
        }
        return ans;
    }

    private int f1(char[] chars1, char[] chars2, int l1, int l2) {
        if(l1<0||l2<0){
            return 0;
        }
        int a = f1(chars1,chars2,l1-1,l2-1);
        int b = f1(chars1,chars2,l1,l2-1);
        int c = f1(chars1,chars2,l1-1,l2);
        int d = 0;
        if(chars1[l1]==chars2[l2]){
            d = f1(chars1,chars2,l1-1,l2-1)+1;
        }
        return Math.max(Math.max(a,b),Math.max(c,d));
    }

}
